//: containers/ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 100 500} Small to keep build testing short
package containers;

import java.util.*;
import java.util.List;

import net.mindview.util.*;

public class ListPerformance
{
    static Random rand = new Random();
    
    static int reps = 1000;
    
    static List<Test<List<Integer>>> tests = new ArrayList<Test<List<Integer>>>();
    
    static List<Test<LinkedList<Integer>>> qTests = new ArrayList<Test<LinkedList<Integer>>>();
    
    static
    {
        tests.add(new Test<List<Integer>>("add")
        {
            int test(List<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int listSize = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    for (int j = 0; j < listSize; j++)
                        list.add(j);
                }
                return loops * listSize;
            }
        });
        tests.add(new Test<List<Integer>>("get")
        {
            int test(List<Integer> list, TestParam tp)
            {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for (int i = 0; i < loops; i++)
                    list.get(rand.nextInt(listSize));
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("set")
        {
            int test(List<Integer> list, TestParam tp)
            {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for (int i = 0; i < loops; i++)
                    list.set(rand.nextInt(listSize), 47);
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("iteradd")
        {
            int test(List<Integer> list, TestParam tp)
            {
                final int LOOPS = 1000000;
                int half = list.size() / 2;
                ListIterator<Integer> it = list.listIterator(half);
                for (int i = 0; i < LOOPS; i++)
                    it.add(47);
                return LOOPS;
            }
        });
        tests.add(new Test<List<Integer>>("insert")
        {
            int test(List<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                for (int i = 0; i < loops; i++)
                    list.add(5, 47); // Minimize random-access cost
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("remove")
        {
            int test(List<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int size = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    list.addAll(new CountingIntegerList(size));
                    while (list.size() > 5)
                        list.remove(5); // Minimize random-access cost
                }
                return loops * size;
            }
        });
        // Tests for queue behavior:
        qTests.add(new Test<LinkedList<Integer>>("addFirst")
        {
            int test(LinkedList<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int size = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    for (int j = 0; j < size; j++)
                        list.addFirst(47);
                }
                return loops * size;
            }
        });
        qTests.add(new Test<LinkedList<Integer>>("addLast")
        {
            int test(LinkedList<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int size = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    for (int j = 0; j < size; j++)
                        list.addLast(47);
                }
                return loops * size;
            }
        });
        qTests.add(new Test<LinkedList<Integer>>("rmFirst")
        {
            int test(LinkedList<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int size = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    list.addAll(new CountingIntegerList(size));
                    while (list.size() > 0)
                        list.removeFirst();
                }
                return loops * size;
            }
        });
        qTests.add(new Test<LinkedList<Integer>>("rmLast")
        {
            int test(LinkedList<Integer> list, TestParam tp)
            {
                int loops = tp.loops;
                int size = tp.size;
                for (int i = 0; i < loops; i++)
                {
                    list.clear();
                    list.addAll(new CountingIntegerList(size));
                    while (list.size() > 0)
                        list.removeLast();
                }
                return loops * size;
            }
        });
    }
    
    static class ListTester extends Tester<List<Integer>>
    {
        public ListTester(List<Integer> container, List<Test<List<Integer>>> tests)
        {
            super(container, tests);
        }
        
        // Fill to the appropriate size before each test:
        @Override
        protected List<Integer> initialize(int size)
        {
            container.clear();
            container.addAll(new CountingIntegerList(size));
            return container;
        }
        
        // Convenience method:
        public static void run(List<Integer> list, List<Test<List<Integer>>> tests)
        {
            new ListTester(list, tests).timedTest();
        }
    }
    
    public static void main(String[] args)
    {
        if (args.length > 0)
            Tester.defaultParams = TestParam.array(args);
        // Can only do these two tests on an array:
        Tester<List<Integer>> arrayTest = new Tester<List<Integer>>(null, tests.subList(1, 3))
        {
            // This will be called before each test. It
            // produces a non-resizeable array-backed list:
            @Override
            protected List<Integer> initialize(int size)
            {
                Integer[] ia = Generated.array(Integer.class, new CountingGenerator.Integer(), size);
                return Arrays.asList(ia);
            }
        };
        arrayTest.setHeadline("Array as List");
        arrayTest.timedTest();
        Tester.defaultParams = TestParam.array(10, 5000, 100, 5000, 1000, 1000, 10000, 200);
        if (args.length > 0)
            Tester.defaultParams = TestParam.array(args);
        ListTester.run(new ArrayList<Integer>(), tests);
        ListTester.run(new LinkedList<Integer>(), tests);
        ListTester.run(new Vector<Integer>(), tests);
        Tester.fieldWidth = 12;
        Tester<LinkedList<Integer>> qTest = new Tester<LinkedList<Integer>>(new LinkedList<Integer>(), qTests);
        qTest.setHeadline("Queue tests");
        qTest.timedTest();
    }
} /*
   * Output: (Sample) --- Array as List --- size get set 10 130 183 100 130 164 1000 129 165 10000 129 165
   * --------------------- ArrayList --------------------- size add get set iteradd insert remove 10 121 139 191 435
   * 3952 446 100 72 141 191 247 3934 296 1000 98 141 194 839 2202 923 10000 122 144 190 6880 14042 7333
   * --------------------- LinkedList --------------------- size add get set iteradd insert remove 10 182 164 198 658
   * 366 262 100 106 202 230 457 108 201 1000 133 1289 1353 430 136 239 10000 172 13648 13187 435 255 239
   * ----------------------- Vector ----------------------- size add get set iteradd insert remove 10 129 145 187 290
   * 3635 253 100 72 144 190 263 3691 292 1000 99 145 193 846 2162 927 10000 108 145 186 6871 14730 7135
   * -------------------- Queue tests -------------------- size addFirst addLast rmFirst rmLast 10 199 163 251 253 100
   * 98 92 180 179 1000 99 93 216 212 10000 111 109 262 384
   */// :~
